/*
 * @Author: szx
 * @Date: 2021-10-17 13:01:27
 * @LastEditTime: 2021-10-17 15:13:46
 * @Description:
 * @FilePath: \leetcode\230\230.go
 */
package main

import (
	"strconv"
	"strings"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 暴力解法，转换为数组
// func kthSmallest(root *TreeNode, k int) int {
// 	var numArr []int
// 	var nodeArr []*TreeNode = []*TreeNode{root}
// 	i := 0
// 	for len(nodeArr) > i {
// 		fmt.Println(nodeArr[i].Val)
// 		numArr = append(numArr, nodeArr[i].Val)
// 		if nodeArr[i].Left != nil {
// 			nodeArr = append(nodeArr, nodeArr[i].Left)
// 		}
// 		if nodeArr[i].Right != nil {
// 			nodeArr = append(nodeArr, nodeArr[i].Right)
// 		}
// 		i++
// 	}
// 	sort.Ints(numArr)
// 	return numArr[k-1]
// }

//艹，题目没有看到二叉搜索树，看了一下以前自己的写法
// func kthSmallest(root *TreeNode, k int) int {
// 	if root == nil {
// 		return 0
// 	}

// 	cnt := count(root.Left)
// 	fmt.Println(cnt)
// 	if cnt >= k {
// 		return kthSmallest(root.Left, k)
// 	} else if k > cnt+1 {
// 		return kthSmallest(root.Right, k-cnt-1)
// 	}
// 	fmt.Println(root.Val)
// 	return root.Val
// }

// func count(node *TreeNode) int {
// 	if node == nil {
// 		return 0
// 	}
// 	return 1 + count(node.Left) + count(node.Right)
// }

//官方解法	中序遍历
// func kthSmallest(root *TreeNode, k int) int {
// 	stack := []*TreeNode{}
// 	for {
// 		for root != nil {
// 			stack = append(stack, root)
// 			root = root.Left
// 		}
// 		stack, root = stack[:len(stack)-1], stack[len(stack)-1]
// 		k--
// 		if k == 0 {
// 			return root.Val
// 		}
// 		root = root.Right
// 	}
// }

// 中序遍历递归法
func kthSmallest(root *TreeNode, k int) int {
	res := 0
	var middleOrder func(root *TreeNode)
	middleOrder = func(root *TreeNode) {
		if root == nil {
			return
		}
		middleOrder(root.Left)
		k--
		if k == 0 {
			res = root.Val
			return
		}
		middleOrder(root.Right)
	}
	middleOrder(root)
	return res
}

//方法二：记录子树的结点数

// go语言生成二叉树
func generateTree(str string) (root *TreeNode) {
	s := strings.TrimLeft(str, "[")
	s = strings.TrimRight(s, "]")
	arr := strings.Split(s, ",")
	if len(arr) == 0 || arr[0] == "null" {
		return
	}
	root = new(TreeNode)
	root.Val, _ = strconv.Atoi(arr[0])
	arr = arr[1:]
	queue := []*TreeNode{root}
	for len(queue) > 0 && len(arr) > 0 {
		node := queue[0]
		queue = queue[1:]

		if arr[0] != "null" {
			node.Left = new(TreeNode)
			node.Left.Val, _ = strconv.Atoi(arr[0])
			queue = append(queue, node.Left)
		}
		arr = arr[1:]
		if len(arr) > 0 {
			if arr[0] != "null" {
				node.Right = new(TreeNode)
				node.Right.Val, _ = strconv.Atoi(arr[0])
				queue = append(queue, node.Right)
			}
			arr = arr[1:]
		}
	}
	return
}

func main() {
	root := generateTree("[5,3,6,2,4,null,null,1]")
	// print(root.Val)
	print(kthSmallest(root, 3))
}
